package leetcode.linkedList;

/**
 * @author liyuhui
 * @date {DATE}
 * @description
 */
public class LinkedListCommon {

    // Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }

        ListNode findNode(int x){

            ListNode curNode = this;
            while(curNode != null){
                if(curNode.val == x)
                    return curNode;
                curNode = curNode.next;
            }
            return null;
        }

        public ListNode (int[] arr){

            if(arr == null || arr.length == 0)
                throw new IllegalArgumentException("arr can not be empty");

            this.val = arr[0];
            ListNode curNode = this;
            for(int i = 1 ; i < arr.length ; i ++){
                curNode.next = new ListNode(arr[i]);
                curNode = curNode.next;
            }
        }
    }

    /**
     * 通过数组创建链表
     * @param arr
     * @param n
     * @return
     */
    public static ListNode createLinkedList(int[] arr, int n){
        if (n == 0) {
            return null;
        }

        ListNode head = new LinkedListCommon().new ListNode(arr[0]);
        ListNode curNode = head;
        for (int i = 1; i < n; i++) {
            curNode.next = new LinkedListCommon().new ListNode(arr[i]);
            curNode = curNode.next;
        }
        return head;
    }

    /**
     * 打印一个链表
     * @param head
     */
    public static void printLinkedNode(ListNode head){
        ListNode curNode = head;
        while (curNode != null){
            System.out.print(curNode.val+"->");
            curNode = curNode.next;
        }
        System.out.print("NULL");
    }

    /**
     * 206 全范围的旋转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {

        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }

    /**
     * 92 m到n范围内的链表反转
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseList(ListNode head,int m,int n) {
        return null;
    }

    /**
     * 25 以k为一组对链表进行反转，不足部分不用反转
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseListInKGroup(ListNode head,int k) {
        return null;
    }


    /**
     * 203 删除链表中某个值的元素，使用虚拟头节点，使得头节点不需要特殊对待
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode cur = dummyHead;
        while(cur.next != null){
            if(cur.next.val == val ){
                ListNode delNode = cur.next;
                cur.next = delNode.next;
            }
            else
                cur = cur.next;
        }

        return dummyHead.next;
    }

    /**
     * 在链表中删除节点，入参是节点不是链表，所以无法得到前一个节点，和上面的删除逻辑不一样了。
     * @param node
     */
    public void deleteNode(ListNode node) {

        if(node == null || node.next == null)
            throw new IllegalArgumentException("node should be valid and can not be the tail node.");

        node.val = node.next.val;
        node.next = node.next.next;
    }

    /**
     * 19 删除倒数第n个节点，n从1开始
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        int length = 0;
        for(ListNode cur = dummyHead.next ; cur != null ; cur = cur.next)
            length ++;

        int k = length - n;
        assert k >= 0;
        ListNode cur = dummyHead;
        for(int i = 0 ; i < k ; i ++)
            cur = cur.next;

        cur.next = cur.next.next;

        return dummyHead.next;
    }

    /**
     * 19 删除倒数第n个节点，n从1开始
     * 采用双指针，添加虚拟头节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        assert (n >=0);

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode p = dummyHead;
        ListNode q = dummyHead;

        //q要移动n+1步，因为是从虚拟头节点开始移动的
        for( int i = 0 ; i < n + 1 ; i ++ ){
            //因为需要访问q的next，所以必须对q判空
            assert q != null;
            q = q.next;
        }

        while(q != null){
            p = p.next;
            q = q.next;
        }

        p.next = p.next.next;

        return dummyHead.next;
    }


    /**
     * 24 swap nodes in pair 对于每两个相邻的节点，交换位置。
     * 同样需要虚拟头节点
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode p = dummyHead;
        while(p.next != null && p.next.next != null ){
            ListNode node1 = p.next;
            ListNode node2 = node1.next;
            ListNode next = node2.next;

            node2.next = node1;
            node1.next = next;
            p.next = node2;

            p = node1;
        }

        return dummyHead.next;
    }


    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        int n = arr.length;

//        ListNode head = createLinkedList(arr,n);
//        printLinkedNode(head);
//
//        ListNode head2 = new LinkedListCommon().reverseList(head);
//        printLinkedNode(head2);

//        ListNode head3 = createLinkedList(arr,n);
//        ListNode head4 = new LinkedListCommon().removeElements(head3,1);
//        printLinkedNode(head4);

        ListNode head5 = createLinkedList(arr,n);
        ListNode head6 = new LinkedListCommon().swapPairs(head5);
        printLinkedNode(head6);


    }

}
